#include "EditDistanceCalculator.hpp"

EditDistanceCalculator::EditDistanceCalculator(const std::vector<UINT32>& first_path,const std::vector<UINT32>& second_path)
{
	std::vector<std::vector<UINT32>> cost_array;
	for(UINT32 i=0;i<=first_path.size();i++)
	{
		cost_array.push_back(std::vector<UINT32>());
		_my_decisions.push_back(std::vector<editing_options>());
		for(UINT32 j=0;j<=second_path.size();j++)
		{
			cost_array[i].push_back(0);
			_my_decisions[i].push_back(MATCH);
			if(i==0)
			{
				_my_decisions[i][j]=LEFT;
				cost_array[i][j]=j;
			}
			if(j==0)
			{
				_my_decisions[i][j]=UP;
				cost_array[i][j]=i;
			}
			if( (i!=0 && j!=0) || (i==0 && j==0))
			{
				_my_decisions[i][j]=MATCH;
			}
		}
	}
	for(UINT32 i=1;i<=first_path.size();i++)
	{
		for(UINT32 j=1;j<=second_path.size();j++)
		{
			if(first_path[i-1]==second_path[j-1])
			{
				cost_array[i][j]=cost_array[i-1][j-1];
				_my_decisions[i][j]=MATCH;
			}
			else
			{
				UINT32 minimum_cost=cost_array[i-1][j-1]+COST_OF_SUBSTITUTING_NODE;
				_my_decisions[i][j]=SWITCH;
				if(minimum_cost>(cost_array[i][j-1]+COST_OF_REMOVING_NODE))
				{
					_my_decisions[i][j]=LEFT;
					minimum_cost=cost_array[i][j-1]+COST_OF_REMOVING_NODE;
				}
				if(minimum_cost>(cost_array[i-1][j]+COST_OF_REMOVING_NODE))
				{
					_my_decisions[i][j]=UP;
					minimum_cost=cost_array[i-1][j]+COST_OF_REMOVING_NODE;
				}
				cost_array[i][j]=minimum_cost;
			}		
		}
	}
	print_costs(cost_array);
	print_decisions();
	printf("The distance is: %d\n",cost_array[first_path.size()-1][second_path.size()-1]);
}

std::string EditDistanceCalculator::decision_to_string(editing_options e) const
{
	if(e==UP)
	{
		return "UP  ";
	}
	if(e==LEFT)
	{
		return "LEFT";
	}
	if(e==MATCH)
	{
		return "MATCH";
	}
	return "SWAP";
}

void EditDistanceCalculator::print_costs(const std::vector<std::vector<UINT32>>& costs) const
{
	for(UINT32 i=0;i<costs.size();i++)
	{
		for(UINT32 j=0;j<costs[i].size();j++)
		{
			printf("%d ",costs[i][j]);
		}
		printf("\n");
	}
}



void EditDistanceCalculator::print_decisions() const
{
	for(UINT32 i=0;i<_my_decisions.size();i++)
	{
		for(UINT32 j=0;j<_my_decisions[i].size();j++)
		{
			printf("%s ",decision_to_string(_my_decisions[i][j]).c_str());
		}
		printf("\n");
	}
}
/*
int LevenshteinDistance(char s[1..m], char t[1..n])
{
	// for all i and j, d[i,j] will hold the Levenshtein distance between
	// the first i characters of s and the first j characters of t;
	// note that d has (m+1)*(n+1) values
	declare int d[0..m, 0..n]

	clear all elements in d // set each element to zero

		// source prefixes can be transformed into empty string by
		// dropping all characters
		for i from 1 to m
		{
			d[i, 0] := i
		}

		// target prefixes can be reached from empty source prefix
		// by inserting every characters
		for j from 1 to n
		{
			d[0, j] := j
		}

		for j from 1 to n
		{
			for i from 1 to m
			{
				if s[i] = t[j] then  //going on the assumption that string indexes are 1-based in your chosen language<!-- not: s[i-1] = t[j-1] -->
					//else you will have to use s[i-1] = t[j-1] Not doing this might throw an IndexOutOfBound error
					d[i, j] := d[i-1, j-1]       // no operation required
				else
					d[i, j] := minimum
					(
					d[i-1, j] + 1,  // a deletion
					d[i, j-1] + 1,  // an insertion
					d[i-1, j-1] + 1 // a substitution
					)
			}
		}

		return d[m,n]
} */